package datastructure;

// Binary Search Tree CLRS version

import java.io.Serializable;

public class BinarySearchTree implements Serializable {
    
    public static class Node implements Serializable {
        public Node left;
        public Node right;
        public String key;
        public Node p;

        public Node () {
            key = "";
            left = null;
            right = null;
            p = null;
        }

        public Node(String n) {
            key = n;
            left = null;
            right = null;
            p = null;
        }

        public Node min() {
            Node temp = this;
            while (temp.left != null) {
                temp = temp.left;
            }
            return temp;
        }

        public Node max() {
            Node temp = this;
            while (temp.right != null) {
                temp = temp.right;
            }
            return temp;
        }
    }

    public Node root;
    
    public BinarySearchTree () {
        
    }

    public BinarySearchTree (Node root) {
        this.root = root;
    }

    
    public void Print(Node x) {
        if (x != null) {
            Print(x.left);
            System.out.print(" " + x.key + " ");
            Print(x.right);
        }
    }

    public boolean isEmpty() {
        if (root == null) {
            return true;
        } else {
            return false;
        }
    }

    public Node search(String k) {
        Node cur = this.root;
        while (cur!= null) {
            if (k.compareTo(cur.key) < 0) {
                cur = cur.left;
            } else if (k.compareTo(cur.key) > 0) {
                cur = cur.right;
            } else {
                return cur;
            }
        }
        return new Node();
    }

    public Node min() {
        Node c = this.root;
        while (c.left != null) {
            c = c.left;
        }
        return c;
    }

    public Node max() {
        Node c = this.root;
        while (c.right != null) {
            c = c.right;
        }
        return c;
    }
    
    public void Insert(Node z) {
         Node y = new Node ();
         Node x = this.root;
         if (isEmpty()) {
             this.root = z;
             return;
         }
         while (x != null) {
             y = x;
             if (z.key.compareTo(x.key) < 0) {
                 x = x.left;
             } else {
                 x = x.right;
             }
         }
         z.p = y;
        if (y == null) {
            this.root = z;
        } else if (z.key.compareTo(y.key) < 0) {
            y.left = z;
        } else {
             y.right = z;
        }
    }

    public void Transplant(Node u, Node v) {
        if (u.p == null) {
            this.root = v;
        } else if (u == u.p.left){
            u.p.left = v;
        } else {
            u.p.right = v;
        }
        if (v != null) {
            v.p = u.p;
        }
    }

    public void Delete(Node z) {
        if (z.left == null) {
            Transplant(z,z.right);
        } else if (z.right == null) {
            Transplant(z,z.left);
        } else {
            Node y = this.min();
            if (y.p != z) {
                Transplant(y,y.right);
                y.right = z.right;
                y.right.p = y;
            }
            Transplant(z,y);
            y.left = z.left;
            y.left.p = y;
        }
    }

    public Node Successor (Node x) {
        if (x.right != null) {
            return x.right.min();
        } else {
            Node y = x.p;
            while (y != null && x != y.right) {
                x = y;
                y = y.p;
            }
            return y;
        }
    }
    
    public Node successor (Node x) {
        if (x.right != null) {
            return x.right.min();
        } else {
            Node y = x.p;
            while (y != null && x != y.right) {
                x= y;
                y = y.p;
            }
            return y;
        }
    }

}
